/*
 * Fichier: RechercheBinaire.java
 * Crée le: 04 janvier 2007.
 * Modifié: 7 juillet 2007.
 * Auteurs: Sébastien ESTIENNE.
 * SiteWeb: http://www.prog-info.org/
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

package chapitre6;



import java.awt.Container;

import javax.swing.JFrame;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;



/**
 * <p>Effectue une recherche binaire avec un tableau trié.</p>
 * @author Sébastien ESTIENNE.
 */
public class RechercheBinaire extends JFrame
{
   /**
    * <p>Serial version UID.</p>
    */
   private static final long serialVersionUID = 1L;


   /**
    * <p>Construction de l'application.</p>
    */
   public RechercheBinaire()
   {
      // Appel du constructeur de la classe JFrame.
      super("Recherche Binaire");

      // Zone de texte de sortie.
      JTextArea zoneSortie = new JTextArea();
      zoneSortie.setEditable(false);

      // Conteneur.
      Container conteneur = getContentPane();

      // Ajoute la zone de sortie au conteneur.
      conteneur.add(new JScrollPane(zoneSortie));

      // Tableau des valeurs à trier.
      int[] tableau = {5, 8, 17, 25, 31, 34, 43, 52, 56, 65};

      // Chaine de caractère de sortie.
      StringBuilder sortie = new StringBuilder();

      // Ajoute à la chaine de sortie les valeurs du tableau.
      sortie.append("Valeurs du tableau:\n");
      for(int i = 0; i < tableau.length; i++)
      {
         sortie.append("  ").append(tableau[i]);
      }
      sortie.append("\n\n");

      // Effectue une recherche binaire.
      int valeur = 17;
      int element = rechercheBinaire(tableau, valeur);
      if(element != -1)
      {
         sortie.append("Valeur ").append(valeur).append(" trouvée à l'élément ").append(element)
               .append("\n");
      }
      else
      {
         sortie.append("Valeur ").append(valeur).append(" introuvable!\n");
      }

      // Met à jour la zone de sortie.
      zoneSortie.setText(sortie.toString());

      // Modifie les propriétés de la fenêtre.
      setSize(300, 150);
      setLocation(100, 100);
      setVisible(true);
      setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
   }


   /**
    * <p>Effectue une recherche binaire.</p>
    * @param tableau Le tableau de valeurs.
    * @param cle L'élément à rechercher.
    * @return L'indice de la clé ou -1 si elle n'a pas été trouvée.
    */
   public int rechercheBinaire(int[] tableau, int cle)
   {
      // Indice de l'élément du bas.
      int bas = 0;

      // Indice de l'élément du haut.
      int haut = tableau.length - 1;

      // Indice de l'élément du milieu.
      int milieu;

      // Parcours jusqu'à l'indice haut.
      while(bas <= haut)
      {
         // Calcule l'élément du milieu.
         milieu = (bas + haut) / 2;

         // La clé a été trouvée.
         if(cle == tableau[milieu])
         {
            return milieu;
         }

         // Modifie l'indice du haut du tableau.
         if(cle < tableau[milieu])
         {
            haut = milieu - 1;
         }
         // Modifie l'indice du bas du tableau.
         else
         {
            bas = milieu + 1;
         }
      }

      // Clé introuvable.
      return -1;
   }


   /**
    * <p>Lance l'application.</p>
    * @param args Les paramètres de la ligne de commande.
    */
   public static void main(String[] args)
   {
      new RechercheBinaire();
   }
}
